L'algorithme d'Euclide étendu - Vers le supérieur

Algorithme d'Euclide étendu

Soit  \(a\) et  \(b\) deux entiers naturels non nuls.

L'algorithme d'Euclide étendu consiste à déterminer simultanément :

• le PGCD de  \(a\) et \(b\)  ;
• un couple \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=\mathrm{PGCD}(a;b)\) .

Pour trouver le PGCD de  \(a\) et \(b\) , il s'agit d'effectuer classiquement l'algorithme d'Euclide.

On note \(r_1\) , \(r_2\) , ..., \(r_{n-2}\) , \(r_{n-1}\) les restes successifs obtenus, avec \(r_{n-1}=\mathrm{PGCD}(a;b)\) , c'est-à-dire que l'algorithme termine en \(n\) étapes ( \(n-1\) étapes de \(r_1\) à \(r_{n-1}\) et une dernière étape pour se rendre compte que le reste suivant vaut \(0\) ).

On note \(q_1\) , \(q_2\) , ..., \(q_{n-2}\) , \(q_{n-1}\) , \(q_n\) les quotients successifs obtenus.
\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|c|}\hline \text{Étape}& \text{Dividende}& \text{Diviseur}& \text{Quotient}& \text{Reste}& \text{Division euclidienne avec reste isolé}\\ \hline 1&a&b&q_1&r_1&r_1=a-bq_1\\ \hline 2&b&r_1&q_2&r_2&r_2=b-r_1q_2\\ \hline 3&r_1&r_2&q_3&r_3&r_3=r_1-r_2q_3\\ \hline \cdots & \cdots & \cdots & \cdots & \cdots & \cdots\\ \hline n-1&r_{n-3}&r_{n-2}&q_{n-1}&r_{n-1}&r_{n-1}=r_{n-3}-r_{n-2}q_{n-1}\\ \hline n&r_{n-2}&r_{n-1}&q_n&r_n=0&r_n=0=r_{n-2}-r_{n-1}q_n\\ \hline\end{array}\end{align*}\)

En notant \(r_{-1}=a\) et \(r_0=b\) , on constate que les divisions euclidiennes en isolant les restes s'écrivent  \(r_k=r_{k-2}-r_{k-1}q_k\)  pour tout  \(k \in \left\lbrace 1 ; ... ; n \right\rbrace\) .

Pour trouver un couple \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=\mathrm{PGCD}(a;b)\) , autrement dit tel que   \(au+bv=r_{n-1}\) , l'idée-clef est que la relation de récurrence ci-dessus sur les restes \(r_k\)  « se transmet » aux coefficients \(u\) et \(v\) de l'égalité \(au+bv=\mathrm{PGCD}(a;b)\) .

Plus précisément, on peut construire deux suites \((u_k)_{k \in \left\lbrace -1;...;n \right\rbrace}\) et \((v_k)_{k \in \left\lbrace -1;...;n \right\rbrace}\) en posant \(\begin{align*}\left\lbrace \begin{array}{l}u_{-1}=1 \\ u_0=0 \\ v_{-1}=0 \\ v_0=1 \\ r_k=au_k+bv_k \ \ \text{ pour tout } k \in \left\lbrace 1 ;...; n \right\rbrace.\end{array} \right.\end{align*}\)   

La relation \(r_k=au_k+bv_k\) est également vraie pour \(k=-1\) et \(k=0\) . En effet,  \(\begin{align*}r_{-1}=a=a \times 1+b \times 0=au_{-1}+bv_{-1}\end{align*}\)  et  \(\begin{align*}r_{0}=a=a \times 0+b \times 1=au_{0}+bv_{0}\end{align*}\) .

De plus, pour tout \(k \in \left\lbrace 1;...;n \right\rbrace\) tel que \(u_{k-2}\) , \(v_{k-2}\) , \(u_{k-1}\) et \(v_{k-1}\) ont déjà été construits,
on a :
\(\begin{align*}r_k& = r_{k-2}-r_{k-1}q_k\\& = au_{k-2}+bv_{k-2}-(au_{k-1}+bv_{k-1})q_k\\& = a(u_{k-2}-u_{k-1}q_k)+b(v_{k-2}-v_{k-1}q_k)\end{align*}\)  
si bien qu'il suffit de poser
\(\begin{align*}u_k=u_{k-2}-u_{k-1}q_k \ \ \text{ et } \ \ v_k=v_{k-2}-v_{k-1}q_k \ \ \text{ pour tout } k \in \left\lbrace 1 ;...; n \right\rbrace\end{align*}\)  et l'on construit ainsi les suites \((u_k)_{k \in \left\lbrace -1;...;n \right\rbrace}\) et \((v_k)_{k \in \left\lbrace -1;...;n \right\rbrace}\) .

En particulier, \(au_{n-1}+bv_{n-1}=r_{n-1}=\mathrm{PGCD}(a;b)\) , donc le couple \((u;v)=(u_{n-1};v_{n-1})\) vérifie l'égalité \(au+bv=\mathrm{PGCD}(a;b)\) .

En pratique, pour calculer les termes des suites \((u_k)\) et \((v_k)\) :

• on applique l'algorithme d'Euclide pour \(a\) et \(b\) ;
• on initialise les suites \((u_k)\) et \((v_k)\) aux rangs \(k=-1\) et \(k=0\) ;
• on se sert des relations de récurrence permettant de calculer les termes \(u_k\) et \(v_k\) à partir des deux rangs précédents et du quotient \(q_k\) (en présentant les calculs sous forme de tableau avec des lignes numérotées à partir de \(L_{-1}\) , on constate que l'opération à faire est \(L_k \leftarrow L_{k-2}-q_kL_{k-1}\) ).
  

Voici une suggestion de présentation de l'algorithme d'Euclide étendu :

Exemples

1. On souhaite déterminer un couple \((u;v) \in \mathbb{Z}^2\) tel que \(156u+42v=\mathrm{PGCD}(156;42)\) .
On utilise l'algorithme d'Euclide étendu.

On en déduit que \(\mathrm{PGCD}(156;42)=6\) et que \(156 \times 3+42 \times (-11)=6\) .

2. On souhaite déterminer un couple \((u;v) \in \mathbb{Z}^2\) tel que \(200u+116v=\mathrm{PGCD}(200;116)\) .
On utilise l'algorithme d'Euclide étendu.

On en déduit que \(\mathrm{PGCD}(200;116)=4\)  et que  \(200 \times (-11)+116 \times 19=4\) .

Remarque

L'algorithme d'Euclide étendu ne donne pas seulement un couple \((u;v) \in \mathbb{Z}^2\) tel que  \(au+bv=\mathrm{PGCD}(a;b)\)  : il donne des couples \((u_k;v_k) \in \mathbb{Z}^2\) tels que \(r_k=au_k+bv_k\) à chaque étape de l'algorithme.